#include "LinkedList.h"

/**
 * Construct the list
 */
template <class Object>
List<Object>::List( ) {
  header = new ListNode<Object>;
}

/**
 * Return an iterator representing the header node.
 */
template <class Object>
ListItr<Object> List<Object>::zeroth( ) const {
  return ListItr<Object>( header );
}

/**
 * Return an iterator representing the first node in the list.
 * This operation is not valid for empty lists.
 */
template <class Object>
ListItr<Object> List<Object>::first( ) const {
  return ListItr<Object>( header->next );
}

/**
 * Test if the list is logically empty.
 * return true if empty, false otherwise.
 */
template <class Object>
bool List<Object>::isEmpty( ) const {
  return header->next == NULL;
}

/**
 * Remove the first occurrence of an item x.
 * Frees the corresponding memory
 */
template <class Object>
void List<Object>::remove( const Object & x ) {
  ListItr<Object> p = findPrevious( x ); // return iterator to the previous node

  if( p.current->next != NULL ) {
    ListNode<Object> *oldNode = p.current->next;
    p.current->next = p.current->next->next;  // Bypass deleted node
    delete oldNode;
  }
}

/**
 * Make the list logically empty.
 */
template <class Object>
void List<Object>::makeEmpty( ) {
  while( !isEmpty( ) )
    remove( first( ).retrieve( ) );
}

/**
 * Destructor
 */
template <class Object>
List<Object>::~List( ) {
  makeEmpty( );
  delete header;
}

/**
 * Deep copy of linked lists.
 * list1 = list2
 */
template <class Object>
const List<Object> & List<Object>::operator=( const List<Object> & rhs ) {
  ListItr<Object> ritr = rhs.first( );
  ListItr<Object> itr = zeroth( );

  if( this != &rhs ) {
    makeEmpty( );
    for( ; !ritr.isPastEnd( ); ritr.advance( ), itr.advance( ) )
      insert( ritr.retrieve( ), itr );
  }
  return *this;
}

/**
 * Copy constructor
 */
template <class Object>
List<Object>::List( const List<Object> & rhs ) {
  header = new ListNode<Object>;
  *this = rhs;
}

/**
 * Insert item x after p.
 */
template <class Object>
void List<Object>::insert( const Object & x, const ListItr<Object> & p ) {
  ListNode<Object>* p_c = p.current;
  ListNode<Object>* p_n = p_c->next;
  ListNode<Object>* add_node = new ListNode<Object>(x);
  add_node->next = p_n;
  p_c->next = add_node; 
}

/**
 * Return iterator corresponding to the first node containing an item x.
 * Iterator isPastEnd if item is not found.
 */
template <class Object>
ListItr<Object> List<Object>::find( const Object & x ) const {
  bool is_x = false;
  ListItr<Object> itr = zeroth();
  while( !is_x && !itr.isPastEnd() ) {
    itr.advance();
    if( !itr.isPastEnd() && x == itr.retrieve() ) {
      is_x = true;
    }    
  }
  return itr;
}

/**
 * Return iterator prior to the first node containing an item x.
 */
template <class Object>
ListItr<Object> List<Object>::findPrevious( const Object & x ) const {
  bool is_x = false;
  ListItr<Object> itr = zeroth();
  ListItr<Object> itr_prev = zeroth();
  while( !is_x && !itr.isPastEnd() ) {
    itr.advance();
    if( !itr.isPastEnd() && x == itr.retrieve() ) {
      is_x = true;
    }
    else {
      itr_prev.advance();
    }   
  }
  return itr_prev;
}
